package com.example.topologicalsorting43;

import java.util.LinkedList;

/**
 * @description kahn算法
 * 如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边
 * 入度为0的顶点表示没有顶点先于它执行
 * @auther lijiewei
 * @date 2022/6/23 10:56
 */
public class Kahn {

    //如果 s 需要先于 t 执行，那就添加一条 s 指向 t 的边
    public void topoSortByKahn(Graph graph) {
        LinkedList<Integer>[] adj = graph.getAdj();
        int v = graph.getV();
        //统计每个顶点的入度
        int[] inDegree = new int[v];
        for (int s = 0; s < v; s++) {
            for (int j = 0; j < adj[s].size(); j++) {
                //i->t
                int t = adj[s].get(j);
                //增加t顶点的入度
                inDegree[t]++;
            }
        }

        //广度优先搜索（BFS）的队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < v; i++) {
            //入度为0，表示可以执行当前顶点
            if (inDegree[i]==0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer s = queue.remove();
            System.out.print("->" + s);
            for (int j = 0; j < adj[s].size(); j++) {
                int t = adj[s].get(j);
                inDegree[t]--;
                if (inDegree[t] == 0) {
                    queue.add(t);
                }

            }
        }

    }


    //如果 s 需要先于 t 执行，那就添加一条 t 指向 s 的边
    public void topoSortByKahn2(Graph graph) {
        //正向邻接表，边s->t表示，s依赖于t, t先于s
        LinkedList<Integer>[] inverseAdj = graph.getAdj();
        int v = graph.getV();

        //统计每个顶点的出度
        int[] outDegree = new int[v];
        for (int s = 0; s < v; s++) {
            outDegree[s] = inverseAdj[s].size();
        }

        //广度优先搜索（BFS）的队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < v; i++) {
            //入度为0，表示可以执行当前顶点
            if (outDegree[i]==0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer s = queue.remove();
            for (int i = 0; i < v; i++) {
                //入度为0，表示可以执行当前顶点
                for (int j = 0; j < inverseAdj[i].size(); j++) {
                    int t = inverseAdj[i].get(j);
                    if (s == t) {
                        outDegree[i]--;
                        if (outDegree[i] == 0) {
                            queue.add(i);
                            System.out.print("->" + s);
                        }
                    }
                }
            }
        }
    }
}
